package com.woniuxy.test;

import java.util.*;

/**
 * @Author: ideaAdmin
 * TODO: 单向链表 是否有环
 * Date: 2022/2/13:17:03
 * Description:
 */

public class SingleLinkedNode<V> {
    private Node head;

    static class Node<V> {
        Node next;
        V value;

        public Node(V value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node<?> node = (Node<?>) o;

            if (next != null ? !next.equals(node.next) : node.next != null) return false;
            return value != null ? value.equals(node.value) : node.value == null;
        }

        @Override
        public int hashCode() {

            int result = 31  + (value != null ? value.hashCode() : 0);
            return result;
        }
    }

    public void addNode(V value, V nextValue) {

        if (head == null) {
            head = new Node(value);
            return;
        }
        Node temp = head;
        for (; temp.next != null; temp = temp.next) {
        }
        Node node = new Node(value);
        temp.next = node;
        node.next = getNode(nextValue);
        return;
    }

    private Node getNode(V nextValue) {
        if (head == null) {
            return null;
        }

        Node temp = head;
        for (; ; ) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.value == nextValue) {
                return temp.next;
            }
            temp = temp.next;

        }
        return null;
    }

    public void forEach() {
        if (head == null) {
            return;
        }
        Node temp = head;
        for (; temp.next != null; temp = temp.next) {
            System.out.println(temp);
        }
    }


    public int isHava() {
        if (head == null) {
            return -1;
        }
        Map<Node,V> map = new HashMap<>();
        Node first = null;//记录第一个进入的环节点
        Boolean isFind = false;
        Node slow = head;
        Node flat = head;
        for (; ; ) {
            if (slow.next == null) {
                return -1;
            }
            slow = slow.next;




            if (flat.next == null || flat.next.next == null) {
                return -1;
            }

            if (map.get(flat) == null || map.get(flat.next) ==null ) {

                map.put(flat, (V) flat.value);
                map.put(flat.next ,(V) flat.next.value);
                System.out.println(flat);

            } else {
                if (!isFind) {
                    first = flat;
                    isFind = true;
                }
            }

            flat = flat.next.next;



            if (flat == slow) {
                return (int) first.value;
            }

        }
    }

    public Node isHava2() {

        Node slow = head;
        Node flat = head;

        while (slow != null && flat.next != null) {
            slow = slow.next;


            if ((flat = flat.next.next) == null) {
                return null;
            }


            if (slow == flat) {
                break;
            }
        }

        //如果有环相遇了就会到这里
        Node temp = head;


        while (temp != slow) {
            temp = temp.next;
            slow = slow.next;
        }

        return temp;
    }


    public static void main(String[] args) {
        SingleLinkedNode<Integer> linkedNode = new SingleLinkedNode<>();
        linkedNode.addNode(1, null);
        linkedNode.addNode(2, null);
        linkedNode.addNode(3, null);
        linkedNode.addNode(4, null);
        linkedNode.addNode(5, null);
        linkedNode.addNode(6, null);
        linkedNode.addNode(7, null);
        linkedNode.addNode(8, 4);
        //System.out.println(linkedNode.getNode(6).hashCode());
        System.out.println(linkedNode.isHava());
//        System.out.println(linkedNode.isHava2());

    }


}
